package com.leetcode.code;

/**
 * TODO  5种方法
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * @author zkingcobra
 */
public class LeetCode0005Java {
    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.println(solution.longestPalindrome2("aabaacc"));
    }

    /**
     * 方法一 滑动窗口：双for循环
     * 方法二 中心扩展算法
     * 方法三 动态规划
     */
    static private class Solution {
        /**
         * 方法二 中心扩展算法
         */
        public String longestPalindrome2(String s) {
            return "";
        }

        /**
         * 方法三 动态规划
         * 1、特殊值的判断
         * TODO 2、创建动态规划表
         * TODO 3、
         *
         * 细节：只是记录下标位置，最后得到答案之后再截取字符串，因为截取字符串有效率问题
         *
         * @author zkingcobra 官方
         */
        public String longestPalindrome3(String s) {

            int length = s.length();

            int maxLength = 0;
            int beginIndex = 0;

            if (length < 2) {
                return s;
            }

            boolean[][] dp = new boolean[length][length];

            // 初始化状态转移方程的对角线的值
            // 单个字符一定是回文，所以为true
            //for (int i = 0; i < length; i++) {
            //    dp[i][i] = true;
            //}

            char[] strChars = s.toCharArray();

            for (int j = 0; j < length; j++) {

                for (int i = 0; i < length; i++) {

                    if (strChars[i] == strChars[j]) {
                        if (j - i < 3) {
                            dp[i][j] = true;
                        } else {
                            // 外部的子串是不是回文由内部的子串决定
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    } else {
                        dp[i][j] = false;
                    }

                    if (dp[i][j] && j - i + 1 > maxLength) {
                        maxLength = j - i + 1;
                        beginIndex = i;
                    }
                }
            }

            //System.out.println(Arrays.deepToString(dp));
            return s.substring(beginIndex, beginIndex + maxLength);
        }
    }
}

//class Solution {
//    public String longestPalindrome(String s) {
//        // 1、暴力法
//        // int len=s.length();
//        // String ans = "";
//        // int max = 0;
//        // for(int i=0;i<len;i++){
//        //   for(int j=i+1;j<=len;j++){
//        //     String sub=s.substring(i,j);
//        //     if(isPalindrome(sub)&&sub.length()>max){// 是回文字符串 记录最大
//        //       ans=sub;
//        //       max=Math.max(max,ans.length());
//        //     }
//        //   }
//        // }
//        // return ans;
//        // // 2、动态规划
//        // if (s == null || s.length() <= 1) return s;
//        // char[] cs = s.toCharArray();
//        // // 定义状态
//        // boolean[][] dp = new boolean[cs.length][cs.length];
//        // // 最长回文子串长度
//        // int maxLen = 1;
//        // // 最长回文子串长度开始索引
//        // int beginIndex = 0;
//        // // 从下到上
//        // for (int i = cs.length - 1; i >= 0; i--) {
//        //     //从左到右
//        //     for (int j = i; j < cs.length; j++) {
//        //         // cs[i,j]的长度
//        //         int len = j - i + 1;
//        //         dp[i][j] = (cs[i] == cs[j] && (len <= 2 || dp[i + 1][j - 1]));
//        //         if (dp[i][j] && maxLen < len) {
//        //             maxLen = len;
//        //             beginIndex = i;
//        //         }
//        //     }
//        // }
//        // return new String(cs,beginIndex,maxLen);
//
//
//        // 中心扩散法
//        //     if (s == null || s.length() <= 1) return s;
//        //     char[] cs = s.toCharArray();
//        //     // 最长回文子串长度
//        //     int maxLen = 1;
//        //     // 最长回文子串长度开始索引
//        //     int beginIndex = 0;
//        //     for (int i = cs.length - 2; i >= 1; i--) {
//        //         // 以i字符为中心向左右两边找回文子串
//        //         int len1 = palindromeLength(cs, i - 1, i + 1);
//        //         // 以i字符右边的间隙为中心向左右两边找回文子串
//        //         int len2 = palindromeLength(cs, i, i + 1);
//        //         // 更新回文子串的长度
//        //         len1=Math.max(len1,len2);
//        //         if(len1>maxLen){
//        //             maxLen=len1;
//        //             beginIndex=i-((maxLen-1)>>>1);
//        //         }
//        //     }
//        //     // 以0号字符右边的间隙为中心的回文子串长度是2
//        //     if(cs[0]==cs[1]&&maxLen<2){
//        //         //cs[0,1]就是最长的回文子串
//        //         beginIndex=0;
//        //         maxLen=2;
//        //     }
//        //    return s.substring(beginIndex,beginIndex+maxLen);
//
//        // 3、中心扩散法优化
//        if (s == null || s.length() <= 1) return s;
//        char[] cs = s.toCharArray();
//        // 最长回文子串长度
//        int maxLen = 1;
//        // 最长回文子串长度开始索引
//        int beginIndex = 0;
//
//        int i = 0;
//
//        while (i < cs.length) {
//            int l = i - 1;
//            // 从第i个字往右边开始扫描找到与cs[i]不想等的字符的位置
//            int r = i;
//            while (++r < cs.length && cs[i] == cs[r]) ;
//            //找到回文子串后 r会成为下一次的i
//            i=r;
//
//            // 从l想左、r向右往两边扩散,找到最长回文子串
//            while (l>=0&&r<cs.length&&cs[l]==cs[r]){
//                l--;
//                r++;
//            }
//            // 扩展结束 更新回文子串的最大长度 s[l+1,r-1];
//            int len=r-l-1;
//            if(len>maxLen){
//                maxLen=len;
//                beginIndex=l+1;
//            }
//        }
//
//
//        return new String(cs, beginIndex, maxLen);
//    }
//
//    /**
//     * 从l开始向左，r开始向右扫描回文字符串
//     *
//     * @param cs
//     * @param l
//     * @param r
//     * @return
//     */
//    private  int palindromeLength(char[] cs, int l, int r) {
//        while (l >= 0 && r < cs.length&&cs[l] == cs[r] ) {
//            l--;
//            r++;
//        }
//        return r - l - 1;
//    }
//
//    //   public boolean isPalindrome(String s){
//    //     int len=s.length();
//    //     for(int i=0;i<len/2;i++){
//    //       if(s.charAt(i)!=s.charAt(len-1-i)){
//    //         return false;
//    //       }
//    //     }
//    //     return true;
//    //   }
//}